package com.shm.leetcode;

/**
 * 200. 岛屿数量
 * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 *
 * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 *
 * 此外，你可以假设该网格的四条边均被水包围。
 *
 *
 *
 * 示例 1：
 *
 * 输入：grid = [
 *   ["1","1","1","1","0"],
 *   ["1","1","0","1","0"],
 *   ["1","1","0","0","0"],
 *   ["0","0","0","0","0"]
 * ]
 * 输出：1
 * 示例 2：
 *
 * 输入：grid = [
 *   ["1","1","0","0","0"],
 *   ["1","1","0","0","0"],
 *   ["0","0","1","0","0"],
 *   ["0","0","0","1","1"]
 * ]
 * 输出：3
 *
 *
 * 提示：
 *
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 300
 * grid[i][j] 的值为 '0' 或 '1'
 * @author SHM
 */
public class NumIslands {
    /**
     * 题意分析：这道题给我们一个矩阵，表示一个二维平面。问我们，被海水包围的陆地一共有多少个。
     *
     * 思路分析：注意到所有的字符 '1' 表示的陆地在这个问题中是连成一片的，而 字符 '0' 表示的水域是连成一片的，这条信息提示我们有「连通性」这样的性质。因此很自然想到使用「并查集」解决这个问题。
     *
     * 设计算法流程：遍历二维矩阵，除了遍历到的单元格要读取出它是「陆地」还是「海水」，还需要看看它周围的区域是否与自己是同类的。
     *
     * 如果当前是「陆地」，尝试与周围的陆地合并一下；
     * 如果当前是「水域」，则需要把所有的「水域」合并在一起。这是因为题目的意思是：所有的 水域为一个整体。因此需要设置了一个虚拟的结点，表示 所有的水域都和这个虚拟结点是连接的 。
     *
     * 注意事项：
     *
     * 针对上面的第 1 点：如果当前是 「陆地」，尝试与周围合并一下，此时周围只要看看「向右」、「向下」 两个方向就可以了，因为这两个方向可以覆盖到所有可以连接的部分；
     * 针对上面的第 2 点：由于设置了「虚拟结点」，最后返回「岛屿个数」的时候，不要忘记将「虚拟结点」代表的「水域」分量去掉，即「岛屿个数 = 连通分量个数 - 1−1」。
     * 参考代码：
     *
     * 说明：
     *
     * 我们这里选取的并查集只实现了「隔代压缩」。在实际工作中，一些优化是否需要使用可以通过测试的结果决定；
     * 把所有的方向，设置在一个二维数组 int[][] directions = new int[][]{{0, 1}, {1, 0}}; 里，是解决二维平面问题常用的技巧；
     * 二维坐标与一维索引的转换需要特别熟练，如果实在想不清楚，举几个具体的例子，在纸上计算一下便不难分析出来。
     *
     * 复杂度分析：
     *
     * 时间复杂度：O(MN \cdot \log MN))O(MN⋅logMN))。其中 MM 和 NN 分别为行数和列数。我们这里只使用了「路径压缩」优化，每次「合并」与「查询」操作的平均时间复杂度为 O(\log MN)O(logMN)；
     * 空间复杂度：O(MN)O(MN)，这是并查集需要使用的空间。
     *
     * 作者：liweiwei1419
     * 链接：https://leetcode-cn.com/leetbook/read/learning-algorithms-with-leetcode/57svnd/
     * @param grid
     * @return
     */
    public int numIslands(char[][] grid) {
        int row = grid.length;
        if(row==0){
            return 0;
        }
        int col = grid[0].length;
        if(col==0){
            return 0;
        }

        int size = row*col;
        UnionFind uf = new UnionFind(size+1);
        int[][] dir = new int[][]{{0,1},{1,0}};
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(grid[i][j]=='1'){
                    for(int[] d:dir){
                        int newX = i+d[0];
                        int newY = j+d[1];
                        if((inArea(newX,newY,row,col)&&grid[newX][newY]=='1')){
                            uf.union(getIndex(i,j,col),getIndex(newX,newY,col));
                        }
                    }
                }else{
                    uf.union(getIndex(i,j,col),size);
                }
            }
        }

        return uf.getCount()-1;
    }

    boolean inArea(int x,int y,int row,int col){
        return x>=0&&y>=0&&x<row&&y<col;
    }

    int getIndex(int x,int y,int col){
        return x*col+y;
    }

    class UnionFind{
        int[] parent;
        int count;
        UnionFind(int n){
            parent = new int[n];
            count = n;
            for(int i=0;i<n;i++){
                parent[i] = i;
            }
        }

        int find(int x){
            if(x!=parent[x]){
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        void union(int x,int y){
            int nX = find(x);
            int nY = find(y);
            if(nX==nY){
                return;
            }
            parent[nY] = nX;
            count--;
        }

        int getCount(){
            return count;
        }
    }



}
